今天將會把昨天實作的樹，加上幾個函式:

• sum(): 所有節點值的總和
• contain(): 查詢是否樹裡有指定要找的值
• size(): 計算樹裡共有幾個節點
• leaves(): 計算樹裡共有幾個葉節點
• min(): 找出值最小的節點
• max(): 找出值最大的節點
• height(): 計算樹的高度

昨天實作的程式碼網址:
https://github.com/a90100/javascript-data-structure/blob/master/day11-tree.js

那我們廢話不多說，直接開始吧!

完成 sum() 函式:

首先將節點的左右子節點的值加起來，其左右子節點透過遞迴又會取得它們子節點的總和，不斷累加得到總和。

sum(node = this.root) {
  if (node === null) {
    return 0
  }
  return node.data +
    this.sum(node.left) +
    this.sum(node.right)
}

完成 contain() 函式:

透過另一個函式_contains()，帶著兩個參數進行判斷，當節點值和查找值相同就回傳true，不然就透過遞迴繼續往左右子節點查找。

contains(value) {
  return this._contains(this.root, value)
}

_contains(node, value) {
  if (node === null) {
    return false
  } else if (node.data === value) { // 當節點值和查找值相同就回傳true
    return true
  }
  return this._contains(node.left, value) ||
    this._contains(node.right, value)
}

完成 size() 函式:

size(node = this.root) {
  if (node === null) {
    return 0
  }
  return 1 + this.size(node.left) + this.size(node.right)
}

完成 leaves() 函式:

leaves(node = this.root) {
  if (node === null) {
    return 0
  }
  // 只有根節點的狀況
  if (node.left === null && node.right === null) {
    return 1
  }
  return this.leaves(node.left) + this.leaves(node.right)
}

完成 max() 函式:

max(node = this.root) {
  if (node === null) {
    return 0
  }
  let leftMax = this.max(node.left)
  let rightMax = this.max(node.right)
  // 父節點比左右子節點大的情況
  if (node.data > leftMax && node.data > rightMax) {
    return node.data
  } else if (leftMax > rightMax) { // 左節點最大
    return leftMax
  } else {
    // 右節點最大
    return rightMax
  }
}

完成 min() 函式:

min(node = this.root) {
  if (node === null) {
    // 預設節點值為樹的最大值
    return tree.max()
  }
  let leftMin = this.min(node.left)
  let rightMin = this.min(node.right)
  // 父節點比左右子節點小的情況
  if (node.data < leftMin && node.data < rightMin) {
    return node.data
  } else if (leftMin < rightMin) {
    return leftMin
  } else {
    return rightMin
  }
}

完成 height() 函式:

透過不斷遞迴，最後一次遞迴的 leftHeight 值為根節點的左子節點高度，rightHeight 值為根節點的右子節點高度，將兩者作比較，大者加1(根節點那層)便是一個樹的高度

height(node = this.root) {
  if (node === null) {
    return 0
  }
  let leftHeight = this.height(node.left)
  let rightHeight = this.height(node.right)
  if (leftHeight > rightHeight) {
    return 1 + leftHeight
  } else {
    return 1 + rightHeight
  }
}

本次文章的完整程式碼在此:
https://github.com/a90100/javascript-data-structure/blob/master/day12-tree-functions.js

下次我們來學習集合 Set，一起加油吧!